package class03;

// 判断一颗树是否是满二叉树
public class Code11_IsFull {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    static class Info {
        int height;
        int size;

        Info(int s, int h) {
            this.height = h;
            this.size = s;
        }
    }

    static boolean isFull(Node head) {
        Info info = process(head);
        return (1 << info.height) - 1 == info.size;
    }

    static Info process(Node head) {
        if (null == head) {
            return new Info(0, 0);
        }

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int size = leftInfo.size + rightInfo.size + 1;
        return new Info(size, height);

    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
//        head.right.right = new Node(7);


        System.out.println(isFull(head));
    }
}
